package main

import "sort"

// 39. 组合总和
//
// https://leetcode.cn/problems/combination-sum/
//
// ```go
func combinationSum(candidates []int, target int) [][]int {
	ans := make([][]int, 0)
	sum := 0
	var dfs func(path []int, pos int)
	dfs = func(path []int, pos int) {
		if sum > target {
			return
		}
		if sum == target {
			tmp := make([]int, len(path))
			copy(tmp, path)
			ans = append(ans, tmp)
			return
		}
		for i := pos; i < len(candidates); i++ {
			path = append(path, candidates[i])
			sum += candidates[i]
			dfs(path, i)
			path = path[:len(path)-1]
			sum -= candidates[i]
		}
	}
	dfs([]int{}, 0)
	return ans
}

//```

// 40. 组合总和 II
//
// https://leetcode.cn/problems/combination-sum-ii/
//
// ```go
func combinationSum2(candidates []int, target int) [][]int {
	sort.Ints(candidates)
	ans := make([][]int, 0)
	sum := 0
	var dfs func(path []int, pos int)
	dfs = func(path []int, pos int) {
		if sum > target {
			return
		}
		if sum == target {
			tmp := make([]int, len(path))
			copy(tmp, path)
			ans = append(ans, tmp)
			return
		}
		mp := map[int]bool{}
		for i := pos; i < len(candidates); i++ {
			if _, ok := mp[candidates[i]]; ok {
				continue
			}
			path = append(path, candidates[i])
			sum += candidates[i]
			mp[candidates[i]] = true
			dfs(path, i+1)
			path = path[:len(path)-1]
			sum -= candidates[i]
			mp[candidates[i]] = false
		}
	}
	dfs([]int{}, 0)
	return ans
}

//```

// 131. 分割回文串
//
// https://leetcode.cn/problems/palindrome-partitioning/
//
// ```go
func partition(s string) [][]string {
	ans := make([][]string, 0)
	var dfs func(path []string, pos int)
	dfs = func(path []string, pos int) {
		if pos == len(s) {
			tmp := make([]string, len(path))
			copy(tmp, path)
			ans = append(ans, tmp)
			return
		}
		for i := pos; i < len(s); i++ {
			if ok := check(pos, i, s); ok {
				path = append(path, s[pos:i+1])
				dfs(path, i+1)
				path = path[:len(path)-1]
			}
		}
	}
	dfs([]string{}, 0)
	return ans
}
func check(i, j int, s string) bool {
	for i <= j {
		if s[i] != s[j] {
			return false
		}
		i++
		j--
	}
	return true
}

//```
